1. Field of the Invention
The present invention relates to methods and systems for administration and utilization of secret fresh random numbers in a networked environment, for example, for digital signature or encryption operations employing the El-Gamal algorithm.
2. Description of the Related Art
Random numbers which are secret and have not been previously used, termed herein "secret fresh random numbers" are utilized in a variety of cryptosystems. One such use is for performing either a digital signature or an encryption in a public key cryptosystem employing the El-Gamal algorithm. In public key cryptosystems a pair of a corresponding public key and a private key may be assigned for each user or client.
The need for secret fresh random numbers when the El-Gamal algorithm is employed for either digital signing or encrypting, is due to its two main weaknesses: 1) none of the random numbers can ever be known by an attacker; and 2) use of the same random number to sign or encrypt two different documents is prohibited. Failure in either case allows an attacker enough information to recover a private key used for a digital signature, or to recover items which have been encrypted using a public key. The recovery of a particular private key by an eavesdropper is considered a catastrophic failure of the system and the recovery of messages sent encrypted with a particular public key may be considered a catastrophic failure depending on the nature of the messages.
A digital signature employing the El-Gamal algorithm utilizes the private key of the signer, a secret fresh random number, and generally the result of applying a secure hash function (such as SHA-1 or RIPEMD) to one or more data items, such as documents, files, programs, or keys (which for simplicity are referred to hereinafter as "documents") to manifest the signer's origination, approval, or certification thereof. The documents to which the signature applies are typically sent along with the signature unless they are already extant at or available to the recipient. At the receiving end a verification takes place which includes utilization of the originator's public key, which has been obtained by the recipient with a certificate from a trustworthy source, and application of the hash function to the documents which are received or otherwise available.
An encryption of data employing the El-Gamal algorithm for the purpose of transmission to a recipient generally involves using the public key of the recipient, which has been obtained with a certificate from a trustworthy source, and a secret fresh random number. The data so encrypted may comprise a symmetric key for one time use which has been used to encrypt in a computationally efficient manner an associated item employing a symmetric encryption algorithm, the encrypted symmetric key and the associated item constituting a package. At the receiving end, the encrypted data or package is decrypted by operations including a decryption using the private key of the recipient. In the case of a package, the decryption using the private key yields the symmetric key which is then used to decrypt the associated item in a computationally efficient manner.
The need for secret fresh random numbers to be available at the user equipment, generally requires the expense of equipping all user equipment with a random number generator based on a natural random phenomenon, such as a reverse biased zener diode exhibiting shot noise in its current. This expense could be avoided if secret fresh random numbers were generated at the server and supplied to the user equipment via the network in a secure manner when needed. However, even if an encrypted channel were set up between the server and the user through an exchange of public keys, and a certificate system were in place to certify the public keys, thereby preventing a man-in-the-middle attack, the freshness requirement would still make the system vulnerable to a block replay attack, in which previous encrypted transmissions, or portions thereof, are replayed by an attacker.
In the aforementioned related patent application, it has been proposed that the private keys of users be maintained at the server in encrypted form, encrypted using user identifying keys, and supplied to the user or client equipment via the network only when needed, for example, for performing a digital signature or encryption. The user identifying keys are derived from user identifying information which is assumed to require the actual presence of the user at the user equipment, in particular a hash of a passphrase entered by the user or biometric information (fingerprint, voiceprint, retina scan, or face scan) measured or scanned by interaction with a physically present user.
In the prior art, also challenge response protocols are known for enabling a server to authenticate a client or user, i.e. to verify that the user possesses his private key, before showing the user any private information. Typically, a challenge response protocol consists of the server generating a random number and sending it in the clear via a network to the user, and the user responding by signing the random number using his private key and sending this signature back to the server. The server can verify the signature (and ensure that it was for the same random number that was sent) using the user's private key and the random number. However, if the El-Gamal algorithm were employed for the signature, there would have to be a random number generator at the user equipment to provide another random number to be used for the signature along with the user's private key. The random number to be signed could not also be used as the random number needed for an El-Gamal signature because of lack of assurance to the user equipment that this random number is both secret and fresh.